This invention relates to communications systems and methods, in particular, to packet communication systems and methods.
[1] ATM Forum, xe2x80x9cTraffic Management Specification Version 4.1xe2x80x9d, AF-TM-0121.000, March 1999.
[2] Stallings, xe2x80x9cHigh-Speed Networksxe2x80x94TCP/IP and ATM Design Principlesxe2x80x9d, Prentice Hall, ISBN 0-13-525965-7, 1998.
The references are provided here to illustrate the state of the art and specific portions of the references are discussed below. The references do not constitute a portion of the invention disclosed herein.
Delay and Delay Variation in Packet Communications Systems
Packet communication systems, or networks, are commonly used for the conveyance of information for data applications. In general, these data applications are insensitive to absolute propagation delay (APDxe2x80x94the time it takes for a packet to propagate through the network) and propagation delay variation (PDVxe2x80x94changes in the APD, also known as jitter or wander).
Packet communications systems can also be used for transport of applications that are sensitive to APD and PDV. Examples include:
Direct voice applications such as VoIP
Leased line applications transported via circuit emulation
Video applications
Certain data protocols such as SNA
FIG. 1A illustrates the general progression from transmit bits 1010 through encapsulation 1014 to transmit packets 1020 through the packet network 1024 to arriving packets 1030 through the JAB 1034 and de-encapsulation 1038 to become a stream of receive bits 1040. Consider a CBR (Constant Bit Rate) application where the bits are created at constant rate R. The rate R remains constant because there are no pauses in the data stream. The application at the receiving end is typically set to receive and process bits at the same rate R. On the path from creation to processing at the receive end the transmit bits 1010 first arrive at a device that encapsulates them into packets and injects the transmit packets 1020 into a packet network 1024 at rate P. Just as the bits arrive from the application at regular intervals (line 1010 of FIG. 1B), the encapsulating device 1014 sends out packets at regular interval (line 1020 of FIG. 1B). However, the intervening packet network is not perfect, so it introduces PDV due to congestion.
In some situations, packets from one set of packets may travel along different routes from point A to point B, increasing PDV. In other cases switches may re-order packets such that packet N, which was sent before packet N+1, arrives after packet N+1 (see for example packets 2 and 3 in line 1030 of FIG. 1B).
Thus, the arriving packets arrive at a rate that over a large period of time averages out to be creation rate P. But from moment to moment, the receive rate varies as congestion in the network causes variation in the amount of time for a packet to traverse the network. The received packets are processed at the receive end and the encapsulated bits are extracted and placed into the JAB.
Definition and Measurement of CTD and CDV
We will base our definitions of APD and PDV on the existing definitions of Cell Transfer Delay (CTD) and Cell Delay Variation (CDV) for Asynchronous Transfer Mode (ATM) devices. Reference [1] defines CTD as the time that it takes for an ATM cell to traverse the network, and CDV as the range between the minimum and maximum values of CTD. The graph depicting a cell transfer delay probability density model shown in FIG. 2 is a reproduction of FIGS. 3-2 from reference [1].
As shown in FIG. 2, there is a fixed delay through the network that gives the lower bound on CTD. There is also a variable component that changes based on network conditions. The variable delay is bounded by a maximum value of CTD, above which cells will be discarded because they are too late to use. The difference between the minimum and maximum values of CTD gives the peak-to-peak value of CDV:
CDVP=max CTDxe2x88x92Fixed Delayxe2x80x83xe2x80x83(1)
Since delay and congestion in the network will change over time, a useful measurement of peak-to-peak CDV should be taken over a long period of time. Another way to look at this is in the frequency domain, where we are looking at the low-frequency components of CDV.
Section 3.6.1.2.1 of [1] gives a xe2x80x9cone pointxe2x80x9d means of measuring an estimate of CDV:
The one-point CDV describes the variability in the pattern of cell arrival events observed at a single measurement point with reference to the negotiated peak rate 1/T (as defined in ITU-T Recommendation I.371).
The one-point CDV for cell k (yk) at a measurement point is defined as the difference between the cell""s reference arrival time (ck) and actual arrival time (ak) at the measurement point: yk=ckxe2x88x92ak. The reference arrival time (ck) is defined as follows:
c0=a0
      c          k      +      1        =      {                                                                      a                                  k                  +                  T                                            ⁢                              xe2x80x83                            ⁢                              if                             ⁢                              xe2x80x83                            ⁢                              c                k                                      ≤                          a              k                                                                                      c                              k                +                T                                      ⁢                          xe2x80x83                        ⁢                          otherwise                                          
Positive values of the one-point CDV correspond to cell clumping; negative values of the one-point CDV correspond to gaps in the cell stream. The reference arrival time defined above eliminates the effect of gaps and provides a measurement of cell clumping.
Note that the value 1/T mentioned above is the same as the rate Constant Bit Rate R mentioned above in connection with FIG. 1A.
Table 1 shows an example of how this method works, where T has a value of 2 and R has a value of 1/T=xc2xd. The estimate of CDV is found by taking the maximum of all of the values of Yk, or 0.19 for the values in Table 1.
Note that while this calculation only provides an estimate CDV, it does have the advantage of not requiring an actual measurement of CTD. Its drawback is that it requires a calculation to be made on each packet in order to create an estimate of CDV.
Note on Time Versus Packets Versus Bytes
In different situations it is convenient to discuss the size of the JAB in terms of time, packets or bytes.
Timexe2x80x94Because APD and PDV are normally discussed in units of microseconds (us) or milliseconds (ms), it may useful to discuss the state of the JAB in terms of time.
Packetsxe2x80x94It is more convenient to talk about the JAB in terms of packets when considering the current depth or fullness of the JAB.
Bytesxe2x80x94The JAB feeds a circuit interface, so it is drained byte-by-byte. Also a discussion of a physical implementation is also more convenient in terms of bytes.
Here are some useful conversion formulas:
JAB Depth (time)=8*JAB Depth (bytes)/Circuit Bit Rate R (bps)
Packet Period (time)=1/Packet Rate P (pps)
Packet Payload (bytes)=Circuit Bit Rate R (bps)*Packet Period (time)/8
JAB Physical Memory (bytes)=JAB Depth (time)*Circuit Bit Rate R (bps)/8
Examples for common circuits are shown in Table 2 below. The packet periods shown are typical, but they could be higher or lower for a given implementation.
This real time measurement of PDV is useful when reported to the user of the service as a metric on the quality of the service provided by the network. Current Service Level Agreements (xe2x80x9cSLAsxe2x80x9d) for a packet service will often include a limit on absolute packet delay (not PDV), lost packets and uptime (service availability). These limits could be absolute, but a guarantee of a certain percentage of service within allowable limits is more common. With the introduction of a standardized method for providing a PDV metric, the PDV values can become a negotiated term in the relevant Service Level Agreement between a supplier of network services and a particular user. This is especially useful in systems that do not measure round trip delay.
The network service provider can hold down PDV by avoiding overloading the network with traffic. A second way to provide low PDV to a particular subset of customers is to implement a priority scheme to give priority to packets covered by a premium SLA.
The real time measurement of PDV can also be used as a trigger for dynamic adjustments to the operation of the equipment at either the transmission or the reception ends. For example, U.S. patent application Ser. No. 10,141,592 for Automatic Adjustment of Buffer Depth for the Correction of Packet Delay Variation makes use of a measurement of packet delay variation as measured by the present application for use in a control scheme to optimize the JAB buffer depth for current network conditions. U.S. patent application Ser. No. 10/141,592 is hereby incorporated by reference.
Note that those of ordinary skill in the art can convert the PDV calculation from packets to bytes, or from packets to remaining time before the buffer would be drained at a constant drain rate. These alternate representations of PDV can be used in Service Level Agreements or in control schemes.
It is therefore an object of the present invention to provide an accurate and computationally simple estimate of PDV.
It is a further object of the present invention to provide an estimate of PDV that reflects recent network conditions and thus tracks changes in network characteristics.
These and other advantages of the present invention are apparent from the drawings and the detailed description that follows.
The present invention is directed to a method of estimating packet delay variation for a packet communication system. Our invention provides an accurate and computationally simple method to estimate PDV. The metric of packet delay variation is useful as a descriptor of the most recent (and presumably current) operating characteristics of the packet communication system. These snapshots describing performance over periods of time can be stored to provide a record, and these individual readings can be combined to form descriptions of the network over longer time ranges. This estimate of PDV can be used to determine if a quality of service for network communications is being delivered. The metric can also be used in control systems to modify the network performance or the performance of the jitter absorption buffer that receives the incoming packets.
Several variations of the method are discussed. In one preferred embodiment, a system that places incoming packets into the JAB is described. An estimate of PDV is made by periodically measuring the range of JAB addresses with stored packets. As described above, the estimate of PDV is proportional to the difference between the largest range of JAB addresses (the xe2x80x9cHigh Water Markxe2x80x9d) and the lowest range of JAB addresses (the xe2x80x9cLow Water Markxe2x80x9d). In the preferred embodiment the result of HWMxe2x88x92LWM is then divided by the drain rate (or multiplied by the time for a packet to be drained). A triggering event causes the calculation of the PDV estimate and the re-initialization of the parameters HWM and LWM. A typical triggering event can be a timer.
Other variations of the PDV estimate can be calculated including a smoothed value of PDV and a PDV value for a sliding window of time.